{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Part I: On-policy learning and SARSA (3 points)](#Part-I:-On-policy-learning-and-SARSA-(3-points))\n",
    "\n",
    "[Part II: Experience replay (4 points)](#Part-II:-experience-replay-(4-points))\n",
    "\n",
    "[Bonus I: TD($ \\lambda $) (5+ points)](#Bonus-I:-TD($\\lambda$)-(5+-points))\n",
    "\n",
    "[Bonus II: More pacman (5+ points)](#Bonus-II:-More-pacman-(5+-points))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I: On-policy learning and SARSA (3 points)\n",
    "\n",
    "_This notebook builds upon `qlearning.ipynb`, or to be exact, generating qlearning.py._\n",
    "\n",
    "The policy we're gonna use is epsilon-greedy policy, where agent takes optimal action with probability $(1-\\epsilon)$, otherwise samples action at random. Note that agent __can__ occasionally sample optimal action during random sampling by pure chance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# In google collab, uncomment this:\n",
    "# !wget https://bit.ly/2FMJP5K -q -O setup.py\n",
    "# !bash setup.py 2>&1 1>stdout.log | tee stderr.log\n",
    "\n",
    "# This code creates a virtual display to draw game images on.\n",
    "# If you are running locally, just ignore it\n",
    "import os\n",
    "if type(os.environ.get(\"DISPLAY\")) is not str or len(os.environ.get(\"DISPLAY\")) == 0:\n",
    "    !bash ../xvfb start\n",
    "    os.environ['DISPLAY'] = ':1'\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you can use code, generated from seminar `seminar_qlearning.ipynb`. Or just copy&paste it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%writefile qlearning.py\n",
    "from collections import defaultdict\n",
    "import random\n",
    "import math\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class QLearningAgent:\n",
    "    def __init__(self, alpha, epsilon, discount, get_legal_actions):\n",
    "        \"\"\"\n",
    "        Q-Learning Agent\n",
    "        based on https://inst.eecs.berkeley.edu/~cs188/sp19/projects.html\n",
    "        Instance variables you have access to\n",
    "          - self.epsilon (exploration prob)\n",
    "          - self.alpha (learning rate)\n",
    "          - self.discount (discount rate aka gamma)\n",
    "\n",
    "        Functions you should use\n",
    "          - self.get_legal_actions(state) {state, hashable -> list of actions, each is hashable}\n",
    "            which returns legal actions for a state\n",
    "          - self.get_qvalue(state,action)\n",
    "            which returns Q(state,action)\n",
    "          - self.set_qvalue(state,action,value)\n",
    "            which sets Q(state,action) := value\n",
    "\n",
    "        !!!Important!!!\n",
    "        Note: please avoid using self._qValues directly. \n",
    "            There's a special self.get_qvalue/set_qvalue for that.\n",
    "        \"\"\"\n",
    "\n",
    "        self.get_legal_actions = get_legal_actions\n",
    "        self._qvalues = defaultdict(lambda: defaultdict(lambda: 0))\n",
    "        self.alpha = alpha\n",
    "        self.epsilon = epsilon\n",
    "        self.discount = discount\n",
    "\n",
    "    def get_qvalue(self, state, action):\n",
    "        \"\"\" Returns Q(state,action) \"\"\"\n",
    "        return self._qvalues[state][action]\n",
    "\n",
    "    def set_qvalue(self, state, action, value):\n",
    "        \"\"\" Sets the Qvalue for [state,action] to the given value \"\"\"\n",
    "        self._qvalues[state][action] = value\n",
    "\n",
    "    #---------------------START OF YOUR CODE---------------------#\n",
    "\n",
    "    def get_value(self, state):\n",
    "        \"\"\"\n",
    "        Compute your agent's estimate of V(s) using current q-values\n",
    "        V(s) = max_over_action Q(state,action) over possible actions.\n",
    "        Note: please take into account that q-values can be negative.\n",
    "        \"\"\"\n",
    "        possible_actions = self.get_legal_actions(state)\n",
    "\n",
    "        # If there are no legal actions, return 0.0\n",
    "        if len(possible_actions) == 0:\n",
    "            return 0.0\n",
    "\n",
    "        <YOUR CODE HERE >\n",
    "\n",
    "        return value\n",
    "\n",
    "    def update(self, state, action, reward, next_state):\n",
    "        \"\"\"\n",
    "        You should do your Q-Value update here:\n",
    "           Q(s,a) := (1 - alpha) * Q(s,a) + alpha * (r + gamma * V(s'))\n",
    "        \"\"\"\n",
    "\n",
    "        # agent parameters\n",
    "        gamma = self.discount\n",
    "        learning_rate = self.alpha\n",
    "\n",
    "        <YOUR CODE HERE >\n",
    "\n",
    "        self.set_qvalue(state, action, < YOUR_QVALUE > )\n",
    "\n",
    "    def get_best_action(self, state):\n",
    "        \"\"\"\n",
    "        Compute the best action to take in a state (using current q-values). \n",
    "        \"\"\"\n",
    "        possible_actions = self.get_legal_actions(state)\n",
    "\n",
    "        # If there are no legal actions, return None\n",
    "        if len(possible_actions) == 0:\n",
    "            return None\n",
    "\n",
    "        <YOUR CODE HERE >\n",
    "\n",
    "        return best_action\n",
    "\n",
    "    def get_action(self, state):\n",
    "        \"\"\"\n",
    "        Compute the action to take in the current state, including exploration.  \n",
    "        With probability self.epsilon, we should take a random action.\n",
    "            otherwise - the best policy action (self.getPolicy).\n",
    "\n",
    "        Note: To pick randomly from a list, use random.choice(list). \n",
    "              To pick True or False with a given probablity, generate uniform number in [0, 1]\n",
    "              and compare it with your probability\n",
    "        \"\"\"\n",
    "\n",
    "        # Pick Action\n",
    "        possible_actions = self.get_legal_actions(state)\n",
    "        action = None\n",
    "\n",
    "        # If there are no legal actions, return None\n",
    "        if len(possible_actions) == 0:\n",
    "            return None\n",
    "\n",
    "        # agent parameters:\n",
    "        epsilon = self.epsilon\n",
    "\n",
    "        <YOUR CODE HERE >\n",
    "\n",
    "        return chosen_action"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qlearning import QLearningAgent\n",
    "\n",
    "\n",
    "class EVSarsaAgent(QLearningAgent):\n",
    "    \"\"\" \n",
    "    An agent that changes some of q-learning functions to implement Expected Value SARSA. \n",
    "    Note: this demo assumes that your implementation of QLearningAgent.update uses get_value(next_state).\n",
    "    If it doesn't, please add\n",
    "        def update(self, state, action, reward, next_state):\n",
    "            and implement it for Expected Value SARSA's V(s')\n",
    "    \"\"\"\n",
    "\n",
    "    def get_value(self, state):\n",
    "        \"\"\" \n",
    "        Returns Vpi for current state under epsilon-greedy policy:\n",
    "          V_{pi}(s) = sum _{over a_i} {pi(a_i | s) * Q(s, a_i)}\n",
    "\n",
    "        Hint: all other methods from QLearningAgent are still accessible.\n",
    "        \"\"\"\n",
    "        epsilon = self.epsilon\n",
    "        possible_actions = self.get_legal_actions(state)\n",
    "\n",
    "        # If there are no legal actions, return 0.0\n",
    "        if len(possible_actions) == 0:\n",
    "            return 0.0\n",
    "\n",
    "        <YOUR CODE HERE: SEE DOCSTRING >\n",
    "\n",
    "        return state_value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cliff World\n",
    "\n",
    "Let's now see how our algorithm compares against q-learning in case where we force agent to explore all the time.\n",
    "\n",
    "<img src=https://github.com/yandexdataschool/Practical_RL/raw/master/yet_another_week/_resource/cliffworld.png width=600>\n",
    "<center><i>image by cs188</i></center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gym\n",
    "import gym.envs.toy_text\n",
    "env = gym.envs.toy_text.CliffWalkingEnv()\n",
    "n_actions = env.action_space.n\n",
    "\n",
    "print(env.__doc__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Our cliffworld has one difference from what's on the image: there is no wall.\n",
    "# Agent can choose to go as close to the cliff as it wishes. x:start, T:exit, C:cliff, o: flat ground\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_and_train(env, agent, t_max=10**4):\n",
    "    \"\"\"This function should \n",
    "    - run a full game, actions given by agent.getAction(s)\n",
    "    - train agent using agent.update(...) whenever possible\n",
    "    - return total reward\"\"\"\n",
    "    total_reward = 0.0\n",
    "    s = env.reset()\n",
    "\n",
    "    for t in range(t_max):\n",
    "        a = agent.get_action(s)\n",
    "\n",
    "        next_s, r, done, _ = env.step(a)\n",
    "        agent.update(s, a, r, next_s)\n",
    "\n",
    "        s = next_s\n",
    "        total_reward += r\n",
    "        if done:\n",
    "            break\n",
    "\n",
    "    return total_reward"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qlearning import QLearningAgent\n",
    "\n",
    "agent_sarsa = EVSarsaAgent(alpha=0.25, epsilon=0.2, discount=0.99,\n",
    "                           get_legal_actions=lambda s: range(n_actions))\n",
    "\n",
    "agent_ql = QLearningAgent(alpha=0.25, epsilon=0.2, discount=0.99,\n",
    "                          get_legal_actions=lambda s: range(n_actions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import clear_output\n",
    "from pandas import DataFrame\n",
    "\n",
    "\n",
    "def moving_average(x, span=100): return DataFrame(\n",
    "    {'x': np.asarray(x)}).x.ewm(span=span).mean().values\n",
    "\n",
    "\n",
    "rewards_sarsa, rewards_ql = [], []\n",
    "\n",
    "for i in range(5000):\n",
    "    rewards_sarsa.append(play_and_train(env, agent_sarsa))\n",
    "    rewards_ql.append(play_and_train(env, agent_ql))\n",
    "    # Note: agent.epsilon stays constant\n",
    "\n",
    "    if i % 100 == 0:\n",
    "        clear_output(True)\n",
    "        print('EVSARSA mean reward =', np.mean(rewards_sarsa[-100:]))\n",
    "        print('QLEARNING mean reward =', np.mean(rewards_ql[-100:]))\n",
    "        plt.title(\"epsilon = %s\" % agent_ql.epsilon)\n",
    "        plt.plot(moving_average(rewards_sarsa), label='ev_sarsa')\n",
    "        plt.plot(moving_average(rewards_ql), label='qlearning')\n",
    "        plt.grid()\n",
    "        plt.legend()\n",
    "        plt.ylim(-500, 0)\n",
    "        plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now see what did the algorithms learn by visualizing their actions at every state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_policy(env, agent):\n",
    "    \"\"\" Prints CliffWalkingEnv policy with arrows. Hard-coded. \"\"\"\n",
    "    n_rows, n_cols = env._cliff.shape\n",
    "\n",
    "    actions = '^>v<'\n",
    "\n",
    "    for yi in range(n_rows):\n",
    "        for xi in range(n_cols):\n",
    "            if env._cliff[yi, xi]:\n",
    "                print(\" C \", end='')\n",
    "            elif (yi * n_cols + xi) == env.start_state_index:\n",
    "                print(\" X \", end='')\n",
    "            elif (yi * n_cols + xi) == n_rows * n_cols - 1:\n",
    "                print(\" T \", end='')\n",
    "            else:\n",
    "                print(\" %s \" %\n",
    "                      actions[agent.get_best_action(yi * n_cols + xi)], end='')\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Q-Learning\")\n",
    "draw_policy(env, agent_ql)\n",
    "\n",
    "print(\"SARSA\")\n",
    "draw_policy(env, agent_sarsa)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### More on SARSA\n",
    "\n",
    "Here are some of the things you can do if you feel like it:\n",
    "\n",
    "* Play with epsilon. See learned how policies change if you set epsilon to higher/lower values (e.g. 0.75).\n",
    "* Expected Value SASRSA for softmax policy __(2pts)__:\n",
    "$$ \\pi(a_i|s) = softmax({Q(s,a_i) \\over \\tau}) = {e ^ {Q(s,a_i)/ \\tau}  \\over {\\sum_{a_j}  e ^{Q(s,a_j) / \\tau }}} $$\n",
    "* Implement N-step algorithms and TD($\\lambda$): see [Sutton's book](http://incompleteideas.net/book/bookdraft2018jan1.pdf) chapter 7 and chapter 12.\n",
    "* Use those algorithms to train on CartPole in previous / next assignment for this week."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II: experience replay (4 points)\n",
    "\n",
    "There's a powerful technique that you can use to improve sample efficiency for off-policy algorithms: [spoiler] Experience replay :)\n",
    "\n",
    "The catch is that you can train Q-learning and EV-SARSA on `<s,a,r,s'>` tuples even if they aren't sampled under current agent's policy. So here's what we're gonna do:\n",
    "\n",
    "<img src=https://github.com/yandexdataschool/Practical_RL/raw/master/yet_another_week/_resource/exp_replay.png width=480>\n",
    "\n",
    "#### Training with experience replay\n",
    "1. Play game, sample `<s,a,r,s'>`.\n",
    "2. Update q-values based on `<s,a,r,s'>`.\n",
    "3. Store `<s,a,r,s'>` transition in a buffer. \n",
    " 3. If buffer is full, delete earliest data.\n",
    "4. Sample K such transitions from that buffer and update q-values based on them.\n",
    "\n",
    "\n",
    "To enable such training, first we must implement a memory structure that would act like such a buffer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# In google collab, uncomment this:\n",
    "# !wget https://bit.ly/2FMJP5K -q -O setup.py\n",
    "# !bash setup.py 2>&1 1>stdout.log | tee stderr.log\n",
    "\n",
    "# This code creates a virtual display to draw game images on.\n",
    "# If you are running locally, just ignore it\n",
    "import os\n",
    "if type(os.environ.get(\"DISPLAY\")) is not str or len(os.environ.get(\"DISPLAY\")) == 0:\n",
    "    !bash ../xvfb start\n",
    "    os.environ['DISPLAY'] = ':1'\n",
    "\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "from IPython.display import clear_output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "\n",
    "class ReplayBuffer(object):\n",
    "    def __init__(self, size):\n",
    "        \"\"\"\n",
    "        Create Replay buffer.\n",
    "        Parameters\n",
    "        ----------\n",
    "        size: int\n",
    "            Max number of transitions to store in the buffer. When the buffer\n",
    "            overflows the old memories are dropped.\n",
    "\n",
    "        Note: for this assignment you can pick any data structure you want.\n",
    "              If you want to keep it simple, you can store a list of tuples of (s, a, r, s') in self._storage\n",
    "              However you may find out there are faster and/or more memory-efficient ways to do so.\n",
    "        \"\"\"\n",
    "        self._storage = []\n",
    "        self._maxsize = size\n",
    "\n",
    "        # OPTIONAL: YOUR CODE\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self._storage)\n",
    "\n",
    "    def add(self, obs_t, action, reward, obs_tp1, done):\n",
    "        '''\n",
    "        Make sure, _storage will not exceed _maxsize. \n",
    "        Make sure, FIFO rule is being followed: the oldest examples has to be removed earlier\n",
    "        '''\n",
    "        data = (obs_t, action, reward, obs_tp1, done)\n",
    "\n",
    "        # add data to storage\n",
    "        <YOUR CODE >\n",
    "\n",
    "    def sample(self, batch_size):\n",
    "        \"\"\"Sample a batch of experiences.\n",
    "        Parameters\n",
    "        ----------\n",
    "        batch_size: int\n",
    "            How many transitions to sample.\n",
    "        Returns\n",
    "        -------\n",
    "        obs_batch: np.array\n",
    "            batch of observations\n",
    "        act_batch: np.array\n",
    "            batch of actions executed given obs_batch\n",
    "        rew_batch: np.array\n",
    "            rewards received as results of executing act_batch\n",
    "        next_obs_batch: np.array\n",
    "            next set of observations seen after executing act_batch\n",
    "        done_mask: np.array\n",
    "            done_mask[i] = 1 if executing act_batch[i] resulted in\n",
    "            the end of an episode and 0 otherwise.\n",
    "        \"\"\"\n",
    "        idxes = <randomly generate batch_size integers to be used as indexes of samples >\n",
    "\n",
    "        # collect <s,a,r,s',done> for each index\n",
    "        <YOUR CODE >\n",
    "\n",
    "        return np.array( < states > ), np.array( < actions > ), np.array( < rewards > ), np.array( < next_states > ), np.array( < is_done > )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some tests to make sure your buffer works right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def obj2arrays(obj):\n",
    "    for x in obj:\n",
    "        yield np.array([x])\n",
    "\n",
    "def obj2sampled(obj):\n",
    "    return tuple(obj2arrays(obj))\n",
    "\n",
    "replay = ReplayBuffer(2)\n",
    "obj1 = (0, 1, 2, 3, True)\n",
    "obj2 = (4, 5, 6, 7, False)\n",
    "replay.add(*obj1)\n",
    "assert replay.sample(\n",
    "    1) == obj2sampled(obj1), \"If there's just one object in buffer, it must be retrieved by buf.sample(1)\"\n",
    "replay.add(*obj2)\n",
    "assert len(replay) == 2, \"Please make sure __len__ methods works as intended.\"\n",
    "replay.add(*obj2)\n",
    "assert len(replay) == 2, \"When buffer is at max capacity, replace objects instead of adding new ones.\"\n",
    "assert tuple(np.unique(a) for a in replay.sample(100)) == obj2sampled(obj2)\n",
    "replay.add(*obj1)\n",
    "assert max(len(np.unique(a)) for a in replay.sample(100)) == 2\n",
    "replay.add(*obj1)\n",
    "assert tuple(np.unique(a) for a in replay.sample(100)) == obj2sampled(obj1)\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's use this buffer to improve training:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gym\n",
    "from qlearning import QLearningAgent\n",
    "\n",
    "env = gym.make(\"Taxi-v2\")\n",
    "n_actions = env.action_space.n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_and_train_with_replay(env, agent, replay=None,\n",
    "                               t_max=10**4, replay_batch_size=32):\n",
    "    \"\"\"\n",
    "    This function should \n",
    "    - run a full game, actions given by agent.getAction(s)\n",
    "    - train agent using agent.update(...) whenever possible\n",
    "    - return total reward\n",
    "    :param replay: ReplayBuffer where agent can store and sample (s,a,r,s',done) tuples.\n",
    "        If None, do not use experience replay\n",
    "    \"\"\"\n",
    "    total_reward = 0.0\n",
    "    s = env.reset()\n",
    "\n",
    "    for t in range(t_max):\n",
    "        # get agent to pick action given state s\n",
    "        a = <YOUR CODE >\n",
    "\n",
    "        next_s, r, done, _ = env.step(a)\n",
    "\n",
    "        # update agent on current transition. Use agent.update\n",
    "        <YOUR CODE >\n",
    "\n",
    "        if replay is not None:\n",
    "            # store current <s,a,r,s'> transition in buffer\n",
    "            <YOUR CODE >\n",
    "\n",
    "            # sample replay_batch_size random transitions from replay,\n",
    "            # then update agent on each of them in a loop\n",
    "            s_, a_, r_, next_s_, done_ = replay.sample(replay_batch_size)\n",
    "            for i in range(replay_batch_size):\n",
    "                <YOUR CODE >\n",
    "\n",
    "        s = next_s\n",
    "        total_reward += r\n",
    "        if done:\n",
    "            break\n",
    "\n",
    "    return total_reward"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create two agents: first will use experience replay, second will not.\n",
    "\n",
    "agent_baseline = QLearningAgent(alpha=0.5, epsilon=0.25, discount=0.99,\n",
    "                                get_legal_actions=lambda s: range(n_actions))\n",
    "\n",
    "agent_replay = QLearningAgent(alpha=0.5, epsilon=0.25, discount=0.99,\n",
    "                              get_legal_actions=lambda s: range(n_actions))\n",
    "\n",
    "replay = ReplayBuffer(1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import clear_output\n",
    "\n",
    "rewards_replay, rewards_baseline = [], []\n",
    "\n",
    "for i in range(1000):\n",
    "    rewards_replay.append(\n",
    "        play_and_train_with_replay(env, agent_replay, replay))\n",
    "    rewards_baseline.append(play_and_train_with_replay(\n",
    "        env, agent_baseline, replay=None))\n",
    "\n",
    "    agent_replay.epsilon *= 0.99\n",
    "    agent_baseline.epsilon *= 0.99\n",
    "\n",
    "    if i % 100 == 0:\n",
    "        clear_output(True)\n",
    "        print('Baseline : eps =', agent_replay.epsilon,\n",
    "              'mean reward =', np.mean(rewards_baseline[-10:]))\n",
    "        print('ExpReplay: eps =', agent_baseline.epsilon,\n",
    "              'mean reward =', np.mean(rewards_replay[-10:]))\n",
    "        plt.plot(moving_average(rewards_replay), label='exp. replay')\n",
    "        plt.plot(moving_average(rewards_baseline), label='baseline')\n",
    "        plt.grid()\n",
    "        plt.legend()\n",
    "        plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### What to expect:\n",
    "\n",
    "Experience replay, if implemented correctly, will improve algorithm's initial convergence a lot, but it shouldn't affect the final performance.\n",
    "\n",
    "### Outro\n",
    "\n",
    "We will use the code you just wrote extensively in the next week of our course. If you're feeling that you need more examples to understand how experience replay works, try using it for binarized state spaces (CartPole or other __[classic control envs](https://gym.openai.com/envs/#classic_control)__).\n",
    "\n",
    "__Next week__ we're gonna explore how q-learning and similar algorithms can be applied for large state spaces, with deep learning models to approximate the Q function.\n",
    "\n",
    "However, __the code you've written__ for this week is already capable of solving many RL problems, and as an added benifit - it is very easy to detach. You can use Q-learning, SARSA and Experience Replay for any RL problems you want to solve - just thow 'em into a file and import the stuff you need."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bonus I: TD($\\lambda$) (5+ points)\n",
    "\n",
    "There's a number of advanced algorithms you can find in week 3 materials (Silver lecture II and/or reading about eligibility traces). One such algorithm is TD(lambda), which is based on the idea of eligibility traces. You can also view it as a combination of N-step updates for alll N.\n",
    "* N-step temporal difference from Sutton's book - [url](http://incompleteideas.net/book/the-book-2nd.html), page 142 / chapter 7 \n",
    "* Eligibility traces from Sutton's book - same url, chapter 12 / page 278\n",
    "* Blog post on eligibility traces - [url](http://pierrelucbacon.com/traces/)\n",
    "\n",
    "Here's a practical algorithm you can start with: [url](https://stackoverflow.com/questions/40862578/how-to-understand-watkinss-q%CE%BB-learning-algorithm-in-suttonbartos-rl-book/40892302)\n",
    "\n",
    "\n",
    "Implementing this algorithm will prove more challenging than q-learning or sarsa, but doing so will earn you a deeper understanding of how value-based methods work [in addition to some bonus points].\n",
    "\n",
    "More kudos for comparing and analyzing TD($\\lambda$) against Q-learning and EV-SARSA in different setups (taxi vs cartpole, constant epsilon vs decreasing epsilon)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bonus II: More pacman (5+ points)\n",
    "\n",
    "__see README.md for software requirements of seminar_py2__\n",
    "\n",
    "Remember seminar_py2 where your vanilla q-learning had hard time solving Pacman even on a small grid? Now's the time to fix that issue.\n",
    "\n",
    "We'll focus on those grids for pacman setup.\n",
    "* python pacman.py -p PacmanQAgent -x N_TRAIN_GAMES -n N_TOTAL_GAMES -l __mediumGrid__\n",
    "* python pacman.py -p PacmanQAgent -x N_TRAIN_GAMES -n N_TOTAL_GAMES -l __mediumClassic__\n",
    "\n",
    "Even if you adjust N_TRAIN_GAMES to 10^5 and N_TOTAL_GAMES to 10^5+100 (100 last games are for test), pacman won't solve those environments\n",
    "\n",
    "The problem with those environments is that they have a large amount of unique states. However, you can devise a smaller environment state by choosing different observation parameters, e.g.:\n",
    " * distance and direction to nearest ghost\n",
    " * where is nearest food\n",
    " * 'center of mass' of all food points (and variance, and whatever)\n",
    " * is there a wall in each direction\n",
    " * and anything else you see fit \n",
    " \n",
    "Here's how to get this information from [state](https://github.com/yandexdataschool/Practical_RL/blob/7a559f8/week03_model_free/seminar_py2/pacman.py#L49),\n",
    " * Get pacman position: [state.getPacmanPosition()](https://github.com/yandexdataschool/Practical_RL/blob/7a559f8/week03_model_free/seminar_py2/pacman.py#L128)\n",
    " * Is there a wall at (x,y)?: [state.hasWall(x,y)](https://github.com/yandexdataschool/Practical_RL/blob/7a559f8/week03_model_free/seminar_py2/pacman.py#L189)\n",
    " * Get ghost positions: [state.getGhostPositions()](https://github.com/yandexdataschool/Practical_RL/blob/7a559f8/week03_model_free/seminar_py2/pacman.py#L144)\n",
    " * Get all food positions: [state.getCapsules()](https://github.com/yandexdataschool/Practical_RL/blob/7a559f8/week03_model_free/seminar_py2/pacman.py#L153)\n",
    " \n",
    "You can call those methods anywhere you see state.\n",
    " * e.g. in [agent.getValue(state)](https://github.com/yandexdataschool/Practical_RL/blob/7a559f8/week03_model_free/seminar_py2/qlearningAgents.py#L52)\n",
    " * Defining a function that extracts all features and calling it in [getQValue](https://github.com/yandexdataschool/Practical_RL/blob/7a559f8/week03_model_free/seminar_py2/qlearningAgents.py#L38) and [setQValue](https://github.com/yandexdataschool/Practical_RL/blob/7a559f8/week03_model_free/seminar_py2/qlearningAgents.py#L44) is probably enough.\n",
    " * You can also change agent parameters. The simplest way is to hard-code them in [PacmanQAgent](https://github.com/yandexdataschool/Practical_RL/blob/7a559f8/week03_model_free/seminar_py2/qlearningAgents.py#L140)\n",
    "\n",
    "Also, don't forget to optimize ```learning_rate```, ```discount``` and ```epsilon``` params of model, this may also help to solve this env."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
